USPTO Patents Application 10689257

PCX world immjBcmwL raj^m organization

INTERNAHONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)

(51) International Patent Cli

odflcatfon 6 ;

(11) International Pul

Mkatkw Number:

WO 96/36941

G06T3/60

Al

(43) International Pul

>Bcatkm Datet 21 No

vernber 1996 (21.11.96)

PCT/US96/0H18
sry 1996 (29.01.96)

15 Mty 1995 (15j05.95)

(72) Inventors: WOBER, Munib, A.; 6 Cliffe Avenue, Havernffl,
MA 01832 (US), HAJJ AHMAD, Ibrahim; Apartment #12,
262 School Street, Sommervllle. MA 02145 (US). RHSCH,
Michael. 53 Nathan Lane, Carlisle. MA 01741 (US).
SUNSHINE, Lot, B.; Apartment #6. 80 Revere Street.
Boston, MA 02114 (US).

(74) Agent: SABOURIN. Robert. A.; Polaroid Corporation. Patent
Dept. 3rd floor. 575 Technology Square, Cambridge, MA
02139-3589 (US).

(SI) Designated States: CA, JP, SO, European patent (AT, BE, CH,
DB, DK, ES. PR, OB. OR, IE, IT, LU, MC NL, PT, SB).

(54) Title! IMAGE ROTATION USING DISCRETE COSINE TRANSFORMS

An linage processing system for skewing or rotating an Image includes an Image
acquisition device, first, second and third memories, a matrix multiplier, control sequencer lock
and an output device. Image rotation is facilitated by rjerfonnmg a series *
on image data points representing the image In a spatial domain. A Bret shearing operation
produces » first sheared image by shearing the image. A second shearing operation produces s
second sheared image by shearing the first sheared image. A third trresrtag operation prc<hice«
a third sheared image corresponding to a routed image by shearing tbe second sheared irnsge.
For each shearing operation the image data points am transformed into DCT coefficients In

data points are generated by talcing a modified inverse discrete even cosine transform (IDCT) of
the DCT coefficients using a modified IDCT basis function frprndm upon either a horizontal

or vertical offset.

1 «-T*h|

000052785

F OR T HE P URPOS ES O QNfLQ YRMATI 0

WO 96/36941 PCT/US96/01418

Inaga rotation using dlscrtto cosine transforms.

This application is a continuation-in-part of U.S. Patent Application No. 08/159,795
filed 30 November 1993 by Munib A. Wooer and Michael L. Reisch. Furthermore, mis
application is related to concurrently filed and commonly assigned U.S. Patent
Applications, assignee nos. C-7940, C-7966, C-8004, C-8005, C-8009 and C-8036.

BACKGROUND OF THR INVTOMTTnM

1. Field of the Invention

The invention relates generally to an improved image processing system and
methods for use with this system. More particularly, the invention relates to a system and
methods thereto for producing a sheared or rotated image.

2. Description of the Prior Art

Images can be thought of as two-dimensional representations of some visual reality
that is distributed in space and/or time. Ordinarily, images are what the human visual
system perceives as variations in external stimuli such as brightness, color, and sometimes
; depth cues. While over the years many techniques have been developed to capture and
reproduce images, their representation as continuous, discrete, or digital signals which can
be manipulated, processed or displayed through the use of computers or other special
purpose electronic hardware is the most recent technique. Now well-established, this latest
technique has a variety of beneficial applications. For instance, while in electronic form,
images cart be enhanced to create special visual effects, restored, coded for transmission to
distant locations, stored in memory (such as on CDROM, DAT, floppy disks, etc.),
reconstructed, displayed, or converted to some other tangible form.

Image processing can occur in various domains such as the spatial domain or the
frequency domain. An image is said to reside in the spatial domain when the values of

the parameters used to describe it, such as luminance, have a direct correspondence with
spatial location. In the frequency domain, the image of the spatial domain may be
represented by a series of frequency components in the form of trigonometric functions
which, when summed for each image data point (Lc, pixel) of the spatial domain, yields
5 the value of the parameter used to characterize the image at mat particular image data
point in the spatial domain. Such a representation may be extended to cover all image
data points of an image.

In the spatial domain, original image data may be represented as a continuous
function of spatial position, designated s 0 (y,x) for the two-dimensional case. For most
10 applications it is acceptable, as well as advantageous, to sample this continuous-space
image along the horizontal and vertical directions at x-iT„ and y-jT v where i and j
are integer indices and T k and T, are the horizontal and vertical sampling periods,
respectively. This yields a matrix of points, aJ$TJR*> which shall be identified henceforth
with the discrete signal designated as s(j,i) for the two-dimensional case where the lower
15 case, s, designates the spatial domain, i is the index of rows, j is the index of columns,
and i and j can be initialized to start at zero. In the frequency domain, matrices can
also be used to mathematically describe an image as a set of transform coefficients (also
referred to as frequency coefficients) which represent frequency data in a transform matrix
conventionally designated, S(v,u), where die upper case, S, designates the frequency
20 domain, u is the index of rows and v is the index of columns.

Spatial image data points may be transformed to the frequency domain using
transformations such as Fourier transforms or discrete cosine transforms. The use of
discrete cosine transforms and inverse discrete cosine transforms for image compression is
well known in the art and, in fact, the practice has been adopted as standard in industry by
25 The Joint Photographic Experts Group (JPEG) and the Motion Picture Expert Group

(MPEG); which were created as part of a joint effort of the Consultative Committee on
International Telegraphy and Telephony (CCITT) and The International Standards
Organization (ISO).

When a discrete even cosine ttansformation (hereinafter DCT) is used, the
30 frequency domain is referred to as the DCT domain and the frequency coefficients are
referred to as DCT coefficients. Conventionally, transforming data from the spatial
domain to the frequency domain is referred to as a forward transformation, whereas

1

WO 96/36941 PCT/US96/01418

transforming data from the frequency domain to the spatial domain is referred to as an
inverse transformation. Hence, a forward discrete cosine transformation is defined as a
transform that maps an image from the original image data points sQ,i) in the spatial
domain to DCT coefficients S(v,u) in the DCT domain according to the basis function of
the forward DCT, whereas an inverse discrete even cosine transformation (or IDCT) is
defined as a transform that maps the DCT coefficients S(v,u) from the DCT domain to
reconstructed image data points 30,0 in the spatial domain according to the basis function
of the IDCT.

Processing an electronically acquired image in an Image processing system
sometimes includes shearing or rotating the image. When an image such as the one
shown in Figure 2 A is rotated, the result is shown in Figure 2B. Rotation is useful in
various applications such as image alignment, described using bilinear interpolation in
"The Image Processing Handbook" by John C. Russ, 1992 CRC Press Inc., pp. 95-100.

The primary object of the current invention is to provide a system for shearing or
rotating an image which is more efficient than existing systems and which is
complementary to international compression standards such as ISO/IEC 10918-1, Section
A.3.3 set by the International Organization of Standards, Joint Photographic Experts Group
and similar standards recognized by the Motion Picture Experts Group. Other objects of
the invention will, in part, appear hereinafter and, in part, be obvious when the following
detailed description is read in conjunction with the drawings.

SUMMARY OF THE INVENTION
An image processing system for skewing (i.e. shearing) or rotating an image
includes: an image acquisition device for acquiring an image signal representing an image;
a first memory for buffering the image signal; a second memory for storing predetermined
discrete cosine transform coefficients; a matrix multiplier for multiplying the image signal
times the predetermined coefficients to produce an output signal; a third memory for
buffering the output signal; control sequencer logic for controlling operation of the image
processing system; and an output device for providing a skewed or rotated image
corresponding to the output signal.

Image rotation according to the inventive system is facilitated by performing a
series of shearing operations on image data points representing an image in the spatial

WO 96/36941 PCT/US96/01418
domain. A first shearing operation produces a first sheared image by shearing the original
image. A second shearing operation produces a second sheared image by shearing the
first sheared image. A third shearing operation produces a third sheared image
corresponding to a rotated image by shearing the second sheared image. For each
shearing operation the image data points are transformed into DCT coefficients in a
frequency domain using a discrete even cosine transform (DCT). Thereafter, skewed
image data points are generated by taking a modified inverse discrete even cosine
transform (IDCT) of the DCT coefficients using a modified IDCT basis function
it upon either a horizontal or vertical offset

BRIEF DESCRIPTION OF THE DRAWINGS
The aforementioned aspects and outer features of the invention are described in
detail in conjunction with the accompanying drawings in which the same reference
numerals are used throughout for denoting corresponding elements and wherein:

Figure 1 is a preferred embodiment of an electronic imaging system according to

Figure 2A is an image; ...

Figure 2B is the image of Figure 2A rotated 90 degrees counterclockwise;
Figure 3 A is a detailed block diagram of the electronic imaging system of Figure

20 1;

Figure 3B is a logic diagram of the matrix multiplier 358 of Figure 3A;
Figure 3C is a timing diagram of signals used and generated by the system of
Figure 3A;

Figure 4A is a flowchart, according to the invention, for horizontally skewing an
image represented in a two-dimensional spatial plane using the system of Figure 3 A;

Figure 4B is a block diagram of the steps of block 8 of Figure 4A for transforming
segments of image data points, 'whereby each segment includes all the image data points
of a row;

Figure 4C is a block diagram of the steps of block 8 of Figure 4A for transforming
segments of image data points, whereby each segment has fewer image data points than
the total number of image data points in the row,

4

WO 96/36941 PCT/US96/01418

Figure 5A is a flowchart, according to the invention, for vertically skewing an
image represented in a two-dimensional spatial plane using the system of Figure 3A;

Figure 5B is a block diagram of the steps of block 46 of Figure 5A for
transforming segments of image data points, whereby each segment includes all the image
data points of a column; and

Figure 5C is a block diagram of the steps of block 46 of Figure 5 A for
transforming segments of image data points, whereby each segment has fewer image data
points than the total number of image data points in a column.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
The present invention relates to an image processing system and associated image
processing methods for shearing or rotating an image of a scene. Figure 1 illustrates one
exemplary embodiment of such a system. As can be seen, Figure 1 illustrates an
electronic image processing system where an image signal source, such as an electronic
still camera 10 or a scanner 12, provides an electronic image signal which represents an
image of the subject (not shown). A computer 18 receives the electronic signal from the
image signal source and thereafter processes the image signal electronically to provide any
number of known image processing functions such as resizing, sharpening, noise removal,
reflection, edge detection or rotation. The processed image can be transmitted, i.e. output,
to any destination device or destination application such as a diskette 16, an user monitor
20, a printer 14, or a remote monitor 26. Operator interaction with the system is
facilitated by use of a keyboard 22 or a mouse 24. Of course, the components shown in
Figure 1 are merely exemplary rather than all inclusive of the many equivalent devices
known by those skilled in the art For instance, the image signal source could include any
device which acts as an image signal source such as an electronic camera, a scanner, a
camcorder, a charge coupled device, a charge injected device, etc. Also, it is noteworthy
that the processing of the image need not necessarily occur solely within the computer 18.
Indeed, various phases or aspects of the image processing could occur in the image signal
source, the computer, or the destination output device.

The image processing system of Figure 1 is further detailed in Figure 3A which
includes an image signal source 350 connected to an image acquisition device 355 which,
in turn, is connected to RAM 356 and control sequencer logic 360. The RAM 356 is also

WO 96/36941 PCT/CS96/01418
connected to a matrix multiplier 358 and die control sequencer logic 360. The control
sequencer logic 360 and the matrix multiplier 358 are connected to one another and are
both connected to ROM 352, ROM 354, ROM 357 and RAM 36* The RAM 364 and the
control sequencer logic 360 are both connected to an image generator 365 which
5 represents any type of device capable of outputting an image, such as a printer, a CRT

display, etc. The control sequencer logic 360 receives a clock pulsetrain 361 from system
clock 362.

Operation of the image processing system of Figure 3 A, useful for image shearing
and rotation, will be more easily understood in view of die following section on DCT
10 mathematics.

This section sets forth certain fundamental concepts relating to forward and inverse

1 5 discrete cosine transforms.

An image is typically made up of a two-dimensional PxQ array of descriptors
called pixels or image data points, where P is the number of rows and Q is the number of
columns repr e sen ting the image. The image can be represented by either image data
points in the spatial domain, or by corresponding DCT coefficients in the frequency

20 domain. A forward DCT generates the DCT coefficients by taking a discrete even cosine
transformation (DECT abbreviated as DCT) of the image data points. Conversely, an .
inverse discrete even cosine transformation (IDECT abbreviated as IDCT) generates the
IDCT coefficients (i.e. reconstructed image data points) by taking an inverse discrete
cosine transformation of the DCT coefficients.

25 A DCT transformation can occur in any number of dimensions as understood by

those skilled in the art In the following one-dimensional example, a row (more
genetically referred to as a segment) of N image data points sQ) can be transformed
from the spatial domain to corresponding DCT coefficients S(v) in the frequency domain
in accordance with equation (1).

WO 96/3*941

PCT/US96/01418

S(v)»C v ||g 80)co8^22L (D

where: 0 & v £ (N -1), v an integer;

s(j) represents the matrix of image data points in the segment;
S(v) represents the corresponding matrix of DCT coefficients;
N represents the number of image data points in the segment;

C v - -L for v = 0; and
C v - 1 for v # 0.

The DCT coefficients S(v) are determined from equation (1) where the normalized cosine
basis terms are derived for a segment having N image data points. The value for S(0) is
determined for v =» 0 by summing each of the image data points sQ) for 0£j£(N-l)
times the cosine terms of the basis function. The value for S(l) is determined as the
summation of image data points sQ) times the cosine terms for v - 1 . This procedure,
which indexes first on v and then on j, is repeated for derivation of DCT coefficients
S(0) through S(N-1).

A modified inverse discrete cosine transformation is mathematically defined in
equation (2) where the one-dimensional matrix S(v) of DCT coefficients is transformed to
a reconstructed matrix l(y) of reconstructed image data points, and y is defined as a real
number within the given range as disclosed and explained in the parent application 795.

1 N r-0 2N

where: 0 i y S (N -1), y a real number,

S(v) represents the matrix of DCT coefficients;

2<y) represents the spatial matrix of reconstructed image data points;

N represents the number of image data points in the segment;

WO 96/36941

rcvvswoiAii

C v - — for v - 0; and
C ¥ - 1 for v * 0.

If the DCT coefficients S(v) of equation (1) are computed from a set of image data points
sQ) and the reconstructed image data points §(y) of equation (2) are computed from the
corresponding DCT coefficients S(v), then sO) ■ My) when y-j, and the process is
referred to as invertible or one-to-one mapping since the reconstructed image data points
of §(y) are identical, within limits, to the original image data points of s(j>. By evaluating
y in equation (2) at other (non-integer) values where 0 £ y £ (N -1), a modified IDCT is
obtained which can be used for various processes such as the interpolation of values
falling between discrete image data points which represent an image.

In determining the values representing the reconstructed image data points S(y)
using equation (2), 3(0) is determined by summing each of the DCT coefficients S(v)
times the cosine terms of the inverse basis function for y - 0. For example, the value for
3(0.5) is determined as the summation of DCT coefficients S(v) times the cosine terms for
y - 0.5. This procedure, which indexes first on y then en v, is repeated for derivation
of all desired reconstructed image data points §(y) where 0 i y £ (N -1).

As earlier noted, the above mathematics can be readily expanded to multiple
dimensions as known by one of ordinary skill in the art. For instance, an image can be
represented in the spatial domain in two-dimensional format as described in parent
application '795, where s(y,x) represents the image data points at real values y and x
in the spatial domain, S(v,u) represents the corresponding DCT coefficients in the
frequency domain, x ranges from 0 to (P-l), y ranges from 0 to (Q-l), P represents the
total number of rows, and Q represents the total number of columns. The image data
points s(ypc) may represent, but are not limited to, parameters such as brightness,
luminance, color or hue.

Both equations (1) and (2) can alternatively be expressed in matrix notation. The
matrix notation (without indices) for equation (1) is:

S - FB s (3)

W096/36M1 PCTAJSJW01418

where S represents the matrix of DCT coefficients, s represents the matrix of image
data points in the spatial domain, and FB represents the forward DCT basis matrix. The
matrix notation for equation (2) is:

3«IBS (4)
where S represents the spatial matrix of reconstructed image data points, and IB
represents the inverse DCT basis matrix for the desired output points (i.e. reconstructed
image data points). Combining matrix equations (3) and (4) will reduce the number of
arithmetic operations as opposed to performing the matrix algebra in two different steps as
previously described. Combining matrix equations (3) and (4) yields:
3 » IB ; (FB • s)
- MB • s (5)
where MB is a combined DCT basis matrix derived from matrix multiplication of the
inverse DCT basis matrix IB times the forward DCT basis matrix FB. The combined
DCT basis matrix MB can be contemporaneously calculated while solving equation (5),
or MB can be precalculated and stored in a look-up table.

2. Image Rrrtarinn Hardware

The preferred embodiment of an image rotation system shown in Figure 3A
includes: image signal source 350; image acquisition device 355; matrix multiplier 358;
random access memory (RAM) image buffers 356 and 364; coefficient read only memory
(ROM) 352, 354 and 357; control sequencer logic 360; master clock 362; and image
generator 365. The master clock 362 produces a master clock signal 361 which is used by
the control sequencer logic 360 to generate clock signals CK1 and CK2. The image
acquisition device 355 could be any hardware for acquiring an image from the source 350,
such as an input port, an A/D converter, etc. Similarly, the image generator 365 could be
any device or system for generating an image from the coefficients stored in RAMs 356 or
364, such as a printer, cathode ray tube, etc. This overall hardware configuration is
general purpose for implementing a variety of matrix product operations.

Referring to Figures 3A, 3B and 3C, the matrix multiplier logic 351 is a fixed
point parallel arithmetic processor capable of computing a 3x3 matrix product in nine CK1
clock cycles. The control sequencer logic 360 generates clock pulses CK1 and CK2 from

the master clock 362. The buffers 356 and 364 are random access memories to buffer the
input and output images; the read only memories 352, 354 and. 357 store precomputed
coefficient matrices; and the control sequencer logic 360 is used to handle control signals,
timing signals, and memory address signals.

5 The matrix multiplier logic 358 is a three fixed-point multiplier accumulator

(MAC) array shown in detail in Figure 3B, with input/output latches and two bi-directional
data buses 372 and 374. The buses 372 and 374 are configurable to transmit data directly
between RAM 356 and RAM 364 in pass through mode, or to transmit dam to the matrix
multiplier logic 358 for processing in process mode according to Truth Table I which

10 defines the functions of data buses 372 and 374 as controlled by signals I„ and I,.

TRUTH TABLE I

lo

I,

372

374

Mode

0

0

IN

OUT

Pass thru

1

0

IN

OUT

Process

0

1

OUT

IN

Process

1

OUT

IN

Pass thru

WO 94/36941 PCT/US9C/01418

The three MAC units include multipliers 400, 402, and 404 followed by the adder
and accumulator pairs {414, 420}, {416, 422}, and {418, 424}, respectively. The outputs
of the accumulators 420, 422 and 424 are stored, respectively, in output latches 426, 428,
and 430. These provide temporary storage to multiplex the results onto the common
output bus 431.

The control sequencer logic 360 controls the memories and data buses as well as
generating appropriate timing signals for the matrix multiplier logic 358. Specifically, the
control sequencer logic 360 provides to RAM memories 356 and 364, respectively,
address data on lines 378 and 382, and read/write (R/W) control data on lines 376 and
380. The control sequencer logic 360 also provides the matrix multiplier logic 358 with
clock signals CK1 and CK2 (derived from master clock signal 361), bus directional signals
1«, I,; output multiplex control signals 0* 0,. and addresses on line 366 for ROMs 352,
354 and 357. The control sequencer logic 360 is easily implemented with a
microcontroller or programmable logic array (PLA), the choice being application
dependent The former is generally more flexible from a programming standpoint but
somewhat higher in cost than the latter.

The operation of the matrix multiplier logic 358 is easily understood by
considering an example of a 3x3 matrix multiplication where C represents a coefficient
matrix, D represents a source image data matrix, and B represents the result of matrix
multiplying C times D. Thus, for

B U B 13 B t3

K D» Du

Bj, B,, B„

X

D 2l D a D„

, D 3i D„ D M

consider the first column of B
column of D,

which is the sums of products of the rows of C and the first

WO 96/36941

PCI7CS96/01418

Cu D n

+ c iPn

ft*

(7)

The timing diagram in Figure 3C shows the relationship of the control and data
signals for this example. The computation proceeds sequentially with the evaluation of
the first, second, and third columns of the B matrix. The process begins with the clearing

5 of the accumulators by the negative RESET pulse received by the matrix multiplier logic
358 from the control sequencer logic 360. The first column of matrix C, that is, C,„ C a „
Cj„ and the first element of the first column of matrix D, that is D,„ are transferred to
input latches 406, 408, 410 and 412 respectively at time T, of clock pulse CKl.
Specifically, C„ is received from ROM 352 by input latch 406, C, 2 is received from ROM

10 354 by input latch 408, C u is received from ROM 357 by input latch 410, and D„ is

received through the bus transmitter 432 from RAM 356 which stores the source image.
The control signals I<, and I, control both the transfer, and the direction of transfer of data
between the matrix multiplier logic 358 and RAMs 356 and 364 according to Truth Table
I. The logic corresponding to Truth Table I is shown by logic 434 and bus transmitter

15 432. At time T, the products C„D,„ Cj,D,„ and C,,D„ are stored in accumulators 420,
422, and 424, respectively. Logic (not shown) for scaling the outputs, i.e. truncating data,
would typically follow the accumulators, as well known by those skilled in the art, to
handle data overflow conditions. At time T 3 the second column of matrix C, that is, C 12 ,
Cjj, and Cjj, and the second element D 2 , of the first column of D are transferred to the

20 input latches 406, 408, 410 and 412, respectively. The partial sum of products, that is,
C„Di,+C,2Psi, C2,D n +Cj,D 2 „ Cj,D„+CjjD 2 , are stored at time T« in accumulators 420,
422, and 424 respectively. Of course, multiplication occurs in multipliers 400, 402, 404
and addition occurs in adders 414, 416, 418. The process repeats for the third column of
C and third element of the first column of D resulting at T 4 in the first column of B

25 having elements {CuDh+C^+C.jDj,}, {CajDn+CjAj+CaDj,} and

{C^Dh+CjjD^+CjjDj,} which were obtained as the sum of the products of the rows C
and the first column of D (see equation (7)).

At the rising edge of clock pulse CK2 at time T, the data from accumulators 420,
422, and 424 is transferred to the output latches 426, 428, and 430, respectively. Output

13.

W096/36W1 PCT/USW/M418
multiplex control signals O, and O, time multiplex the outputs of the output latches onto
data bus 372 or 374 in accordance with Truth Table I at times T„ T„ and T 10 . The whole
process is repeated in this fashion for computing the remaining second and third columns
of B in equation (6).

5 The above implementation of the hardware of Figures 3A and 3B describes one

complete shear of the image data points representing the image. Of course, to properly
carry out image rotation as described in the following section on miage Rotation
Methodology, three shears are required. Thus, the data points stored in RAM 364 after
one shearing operation should be transferred fa pass-through mode (see Truth Table f)

10 from RAM 364 through matrix multiplier 358 to RAM 356. The shearing process repeats
until all three shears have been accomplished and the resultant image data points stored in
RAM 364 represent the rotated image.

In sum, the matrix multiplier logic 358 of Figure 3A is ideally suited to perform
image rotation. The first and second rows of both the horizontal and vertical transform

15 matrices are stored in ROMs 352 and 354, respectively; the source image is stored in

RAM 356; and the rotated image is stored in RAM 364. Note that the matrix multiplier
logic 358 is clearly able to handle products of matrices other than order three. For
example, vector products, as well as 2x2 matrix products can be easily processed.

Of course functional equivalents of the above described components would work

20 equally well in implementing the image rotation device. For instance, the memories are
not limited to RAMs or ROMs but include any type of known memory devices. Also as
earlier noted, the coefficients stored in ROMs 352, 354 and 357 could be precalculated as
a combined reconstruction vector to be multiplied times the source pixels received from
RAM 356 rather than as precalculated modified EDCT basis coefficients to be multiplied

25 times precalculated DCT coefficients stored in RAM 356.

t.

GO005278S

wo9«/3694i wcmmmua

3. Image Rotation Methodology

The image processing system of Figure 3 A provides image rotation in the DCT
domain by decomposing the rotation operation into a sequence of shearing operations. A
rotation matrix can be represented in the form:

tcosd -smOj
smO cos6 )

5

where 9 is the desired angle of rotation. This rotation matrix can be decomposed into a
product of shearing matrices where

'".63

represents a vertical shearing matrix for shearing an image vertically and

10

represents a horizontal shearing matrix for shearing an image horizontally. The rotation
matrix can be decomposed as either

[cose -sineWl a ) (l o\ (l a] (6)
Unfi cosej Ip 1 J lp i) \0 lj

15

where die vertical shearing factor is defined as B - sin 6 and die horizontal shearing
factor is denned as a = - tan (9/2), or,

■H -^l - f 1 °] f 1 A f 1 °] co

isme cos8 J \p 1 J \0 lj \p lj

20

where the vertical shearing factor is defined as P =- tan ( 9/2) and the horizontal
shearing factor is defined as a --sin 6.

In the case of the decomposition in equation (6), an input image is rotated by an
angle 9 by (1) horizontally shearing the input image to produce a first skewed image (2)
25 vertically shearing the first skewed image to produce a second skewed image, and (3)
horizontally shearing the second skewed image to produce the rotated image.

WO 96/3*941 PCI7US96/0i41§

In the case of the decomposition in equation (7), an input image is rotated by an
angle 9 by (1) vertically shearing the input image to produce a first skewed image (2)
horizontally shearing die first skewed image to produce a second skewed image, and (3)
vertically shearing the second skewed image to produce the rotated image.
5 In the general case of image rotation using the decomposition in either equation (6)

or (7), the image rotation method includes the steps of:

(!) providing a first spatial matrix of pixels representing an original image in two
dimensions;

(ii) generating a first shear matrix (also referred to as a skew matrix)
10 corresponding to a first skewed image by shearing the first spatial matrix in a first

dimension;

(Hi) generating a second shear matrix corresponding to a second skewed image
by shearing the first shear matrix in a second dimension; and

(iv) generating a third shear matrix corresponding to a third skewed image, i.e.
15 the image rotated by 6, by shearing the second shear matrix in the first dimension.

A major advantage behind performing the shearing in the above manner is the decoupling
of the horizontal and vertical shears, so that a new sampling grid for each shear step need
only be computed in one dimension. Of course, it is not always necessary or desirable to
shear all pixels of an image. In some instance, shearing a portion of the image is
20 sufficient

An image, represented as s(j,i), can be horizontally sheared as shown in Figure 4A
according to the decomposition in equation (6), where 0 is initialized to a desired angle of
rotation, and the row index r is initialized to zero in block 440. P represents the total
number of rows in the image, and Q represents the total number of columns in the

25 image. Since the image is represented as a PxQ matrix, Q also represents the total
number of image data points in each row. Thus, if a segment size equal to the total
number of pixels in a row is selected, then Q columns in Figure 4A equates with N
image data points in equation (1). In block 442, the horizontal shearing factor a - -
tan(9/2) is calculated and in block 444 the horizontal offset AH is determined as the

30 product of the horizontal shearing factor a times the row index r (i.e. AH - ctr).

In block 446 all pixels in row r are shifted by the same horizontal offset AH.
This is done using the process shown in either Figure 4B or 4C. Figure 4B shows the

i

000052785

WO 96/36941

PCT/US96J01418

appropriate steps for

and

a complete row of image data points in one

step whereas Figure 4C shows the appropriate steps for shifting and transforming a row of
image data points by first dividing the row into N point segments, where N is equal to
or less man the number of pixels in a row. Specifically, the DCT transformation process

5 of Figure 4C is performed by taking DCT transformations of adjacent three-point segments
(i.e. N-3) of image data points having a one-point overlap, whereas the DCT
transformation process of Figure 4B is performed by taking DCT transformations for N-Q.

For either Figure 4B or 4C, each pixel of a given row is shifted by the value of the
horizontal offset AH, which is generally not an integer and can be written as:

10 AH - I ah + 4h

where I w and f^ are the integer and fractional parts of AH, respectively. The shift by
AH can be implemented by computing the interpolated values of the IDCT coefficients
5(y) as though the shift was by and then just offsetting the result by 1^ in the output
matrix. The modified IDCT of equation (2) is then evaluated according to equation (8) to

15 compensate for the fractional part of the horizontal offset, f m .

20

25

where:

0 < G-f*d * (N-l), j an integer,

0 < y £ (N-l), y a real number,

S(v) represents the matrix of DCT coefficients;

§(y) represents the spatial matrix of reconstructed (skewed) image data

points;

§ 0-1) represents §<y) with the y index changed to integer values;
N represents the number of DCT coefficients in the segment;

WO 9606941

C„ - -L for v - 0; and
C v -1 for v + 0.

For the above values of y, there will be (N-l) reconstructed image data points
S whether N represents either the total number of pixels in the row (Fig. 4B) or a lesser
number of pixels of a segment (Fig. 4C). All of the reconstructed image data points will
lie in the spatial range between 3(0) and S(N-1).

In block 448, the row index r is incremented by one, then tested against the total
number of rows P in block 450. If r < P. then the sequence of steps in blocks 444-450

10 is repeated. In effect, each pass through blocks 444-450 skews another row of pixels of
the image. Completion of the shearing of each row in the image results in a first
horizontally skewed image.

The preferred implementation of the above skewing method is achieved by
segmenting the desired row of the image into smaller, overlapping blocks of image data

15 points of size N as shown by the steps of Fig. 4C. It has been empirically determined
that a three or four point DCT with a one-point overlap between adjacent segments
provides excellent results (although any segment size N could be selected). When N-Z,
the speed of computation is high but the accuracy of the results suffers. In contrast when
N-8, the accuracy of the interpolation is high but computational speed is slow. Thus, a

20 preferred embodiment provides a row of image data points subjected to a three-point DCT
according to equation (1) when N-3. Thus, N is set to 3 and the column index c is
initialized to zero in block 458. Row r equates to index i and column c equates to
index j in DCT equations (1) and (8) for an image represented spatially as sQ,i). In
block 460, a DCT according to equation (1) is taken of the first three-point segment of

25 row r, namely s(0), s(l) and s(2). The modified IDCT of equation (8) is used in block
462 to reconstruct spatial image data points 3(0) and 3(1). The reconstructed image data
point 8(2), which is overlapped with a second three-point segment, will be calculated and
included in the second segment of reconstructed image data points. The values of 3(0)
and 3(1) are stored or otherwise saved as reconstructed image data points of the

30 horizontally skewed image. In block 464 the column index c is incremented to c -

IT

I

300052785

PCT/US96/01418

WO 96/36941 PCT/USM/M418
c+N-1. In block 466, it is determined whether or not all of the pixels have been processed
for row r. If all of the pixels have been processed, then the decision block is answered in
the affirmative and the overall horizontal shearing process continues in block 448. If on
the other hand, all of the pixels in row r have not been processed, then the DCT
5 transformation of the next N-point segment continues in block 460. In the current

example, c - 2, and the next three-point DCT occurs on pixels in the same row spatially
located at s(2), s(3) and s(4). The modified IDCT of equation (8) is used to reconstruct
spatial image data points 8(2) and §(3) in block 462. The values of S(2) and 3(3) are saved
for the matrix of reconstructed image data points. The above overlapping procedure

10 continues for each pixel of the image resulting in a first horizontally skewed image
represented as a matrix of reconstructed image data points.

Once the image is horizontally skewed to form the first horizontally skewed image
according to decomposition equation (6), then the second step of equation (6) calls for
vertically shearing the first horizontally skewed image. This can be accomplished by

15 following the steps of Figure 5 A.

In block 500, 6 maintains the same value selected for horizontal skewing, and the
column index c is initialized to zero. Since the image is represented as a PxQ matrix, P
also represents the total number of pixels in each column. In block 502, the vertical
shearing factor (J - sinO is calculated and in block 504 the vertical offset AV is

20 determined as the product of the vertical shearing factor p times the column index c (i.e.
AV-pc).

In block 506 all pixels in column c are shifted by the same vertical offset AV.
This is done using the process shown in either Figure 5B or 5C. Figure 5B shows the
appropriate steps for shifting and transforming a complete column of image data points in

25 one step whereas Figure 5C shows the appropriate steps for shifting and transforming a
column of image data points by first dividing the column into N point segments, where
N is equal to or less than the number of pixels in a column. Specifically, the DCT
transformation process of Figure 5C is performed for the present embodiment by taking
DCT transformations of adjacent three-point segments (Le. N-3) of image data points

30 having a one-point overlap, whereas the DCT transformation process of Figure 5B is
performed by taking DCT transformations for N-P.

I*

W09W36941 PCTAJS9<y01418

For either Figure SB or 5C, each pixel of a given column is shifted by the value of
the vertical offset AV, which is generally not an integer and can be written as:
AV-I 4V + f AV

where I 4V and f 4V are the integer and fractional parts of AV, respectively. The shift by
AV can be implemented by computing the interpolated values of the IDCT coefficients
§(y) as though the shift was by f 4V and then just offsetting the result by I AV in the output
matrix. The modified IDCT of equation (2) is then evaluated according to equation (9) to
b for the fractional part of the vertical offset, f AV .

» 0-D » W U*,- J| g c, sm «=''.«-v» <»>

15 points:

where: 0 < (j-f 4 v) * (N-l), j an i

0 < y £ (N-l), y a real i
S(v) represents the matrix of DCT coefficients;
S(y) represents the spatial matrix of reconstructed (skewed) image data

§ 0-1) represents S(y) with the y index changed to integer values;
N represents the number of DCT coefficients in the segment;

C v - -L forv«6;and
ft

C ¥ «lforv#0.

For the above values of y, there will be (N-l) reconstructed image data points
whether N represents either the total number of pixels in the column (Fig. 5B) or a lesser
number of pixels of a segment (Fig. 5C). All of the reconstructed image data points will
lie in the spatial range between 3(0) and S(N-1).

In block 508, the column index c is incremented by one, then tested against the
total number of columns Q in block 510. If c < Q, then the sequence of steps in blocks
504-510 is repeated. In effect, each pass through blocks 504-510 skews another column

000032783

W096/365M1 PCT/US94/01418
of pixels of the image. Completion of the shearing of each column in the first
horizontally skewed image results in a first vertically skewed image.

As described above, the current example uses a three-point DCT with a one-point
overlap between adjacent segments. Specifically, a column of image data points is
subjected to a three-point DCT according to equation (1) when N-3. Thus, N is set to 3
and the row index r is initialized to zero in block 518. Row r equates to index i and
column c equates to index j in DCT equations (1) and (8) for an image represented
spatially as $0,0- hi block 520, a DCT according to equation (I) is taken of the first
three-point segment of column c, namely s(0), s(l) and s(2). The modified IDCT of
equation (8) is used in block 522 to reconstruct spatial image data points 1(0) and §(1).
The reconstructed image data point S(2), which is overlapped with a second three-point
segment, will be calculated and included in the second segment of reconstructed image
data points. The values of 3(0) and 8(1) are stored or otherwise saved as reconstructed
image data points of the vertically skewed image. In block 524 the row index r is
incremented to r - r+N-1. In block 526, it is determined whether or not all of the pixels
have been processed for column c. If all of the pixels have been processed, then the
decision block 526 is answered in the affirmative and the overall horizontal shearing
process continues in block 508. If on the other hand, all of the pixels in column c have
not been processed, then the DCT transformation of the next N-point segment continues
in block 520. In the current example, the value of r in block 526 is 2 after processing
the first three-point segment, and the next three-point DCT occurs on pixels in the same
column spatially located at s(2), s(3) and s(4). The modified IDCT of equation (8) is used
to reconstruct spatial image data points 8(2) and S(3) in block 522. The values of 9(2) and
3(3) are saved for the matrix of reconstructed image data points. The above overlapping
procedure continues for each pixel of the- image resulting in a first vertically skewed
image represented as a matrix of reconstructed image data points.

Once the first vertically skewed image is obtained by vertically skewing the first
horizontally skewed image, then the final step for rotating the image by an angle 0,
according to decomposition of the rotation matrix as shown in equation (6), can be
implemented by horizontally skewing the first vertically skewed matrix in an effort to
obtain a second horizontally skewed matrix. This is done in the same manner as described
above in accordance with the process shown in Figures 4 A, 4B and 4C for obtaining the

WO 96/36941 PCMJS96/01418
first horizontally skewed matrix. For the preferred embodiment using the three-point DCT
with a one-point overlap, the processing steps of Figure SC are followed. The second
horizontally sheared image (represented by the second horizontally skewed matrix), which
is obtained by horizontally skewing the first vertically skewed image, corresponds to the
original image rotated by the selected angle 6.

The same procedures described above can be applied when rotating the image by
decomposition of the rotation matrix of equation (7). However, the value of the horizontal
shearing factor of block 442 in Figure 4A will be changed to a - -sin6, and the value of
the vertical shearing factor of block 502 in Figure 5A will be changed to p - tan(0/2).

It is to be understood that the above described embodiments are merely illustrative
of the present invention and represent a limited number of the possible specific
embodiments that can provide applications of the principles of the invention. Numerous
and varied other arrangements, which are structurally or operationally equivalent to the
claims as described herein, may be readily devised in accordance with these principles by
those skilled in the art without departing from the spirit and scope of the invention as
claimed.

. Claims:

1. An image processing system for skewing or rotating an image received
from an image signal source and represented as an image signal, said system comprising:

means for acquiring the image signal from the image signal source;
a first memory for buffering said acquired image signal;

a second memory for storing predetermined discrete cosine transform coefficients;
a matrix multiplier for multiplying said image signal retrieved from said first
memory times said predetermined coefficients to produce an output signal;
a third memory for buffering said output signal;

control sequencer logic for controlling operation of said image processing system;

and

an output device for retrieving said output signal from said third memory and
providing a skewed or rotated image corresponding to said output signal.

2. An image processing device for skewing a segment of an image, said image
represented by pixels aligned in rows and columns in a spatial domain, said device
comprising:

means for selecting an image rotation angle;
means for initializing one of a column index and a row index;
means for determining a shear factor trigonometrically related to said image
rotation angle;

means for determining an offset related to said shear factor and said one of the
column index and the row index;

means for generating DCT coefficients of the segment of pixels related to said one
of die column index and the row index by taking a forward discrete even cosine
transformation (DCT) of said segment; and

means for generating modified IDCT coefficients of said segment by taking a
modified inverse discrete even cosine transformation (IDCT) of said DCT coefficients,
said modified IDCT coefficients corresponding to said skewed segment of the image.

WO 96/3694 1 PCT/US9«m418

3. The image processing method of claim 2, further comprising means for
generating said skewed segment of the image in response to said modified IDCT

4. An image processing device for skewing an image represented by pixels
aligned in rows and columns in a spatial domain, said method comprising:

means for selecting an image rotation angle 9;

means for initializing an integer row index r,

means for determining a horizontal shear factor a - -tan(6/2); .

means for determining a horizontal offset AH defined as the product of the
horizontal shear factor a times the row index r,

means for generating DCT coefficients of segments of pixels related to said row
index r by taking a forward discrete even cosine transformation (DCT) of said segments;

means for generating modified IDCT coefficients corresponding to shifted pixels by
taking a modified inverse discrete even cosine transformation (IDCT) of said DCT
coefficients of said segments using a modified IDCT basis matrix dependent upon said
horizontal offset; and

means for incrementing said row index r by one so that a next row of said image
can be processed.

5. The image processing device of claim 4, further comprising means for
generating said skewed image in response to said modified IDCT coefficients.

6. An image processing device for skewing an image represented by pixels
aligned in rows and columns in a spatial domain, said device comprising:

means for selecting a predetermined image rotation angle 8;
means for initializing an integer column index c;
means for determining a vertical shear factor P - sin 6;

means for determining a vertical offset A V defined as the product of the vertical
shear factor 0 times the column index c;

means for generating DCT coefficients of segments of pixels related to said column
index c by taking a forward discrete even cosine transformation (DCT) of said segments;

i

300052785

means for generating modified IDCT coefficients corresponding to shifted pixels by
taking a modified inverse discrete cosine transformation (IDCT) of said DCT coefficients
of said segments using a modified IDCT basis function dependent upon said vertical
offset; and

means for incrementing said column index c by one so that a next column of said
image can be processed.

7. The image processing device of claim 6, further comprising means for
generating said skewed image in response to said modified IDCT coefficients.

8. An image processing device which provides an output image rotated
relative to an input image by an angle 8, said device comprising:

(a) means for providing an array of rows and columns of pixels representing the
input image;

(b) means for producing a first sheared image by performing a first shearing
operation on said array, said means for producing a first sheared image comprising:

(bl) means for initializing an integer row index r,

(b2) means for determining a horizontal shear factor a - -tan(6/2);

(b3) means for determining a horizontal offset AH defined as the product of
the horizontal shear factor a times the row index r,

(b4) means for generating DCT coefficients, of a segment of pixels related
to said row index r, by taking a forward discrete even cosine transformation
(DCT) of said segment;

(b3) means for generating modified IDCT coefficients, corresponding to
shifted pixels, by performing a modified inverse discrete even cosine
transformation (IDCT) of said DCT coefficients of said row index r using a
modified IDCT basis function dependent upon said horizontal offset;

(b6) means for incrementing said row index r by one so that a next row of
said image can be processed;

(c) means for producing a second sheared image by performing a second shearing
operation on said first sheared image, said means for producing a second sheared image
comprising:

a4

W096M6941 PCT/US96/01418

(cl) means for initializing an integer column index c;

(c2) means for determining a vertical shear factor P - sin 9;

(c3) means for determining a vertical offset AV defined as the product of
the vertical shear factor 3 times the column index c;

(c4) means for generating DCT coefficients of a segment of pixels related
to said column index c by taking a forward discrete even cosine transformation
(DCT) of said segment;

(c5) means for generating modified IDCT coefficients, corresponding to
shifted pixels, by performing a modified inverse discrete cosine transformation
(IDCT) of said DCT coefficients of said column index c using a modified IDCT
basis function dependent upon said vertical offset;

(c6) means for incrementing said column index c by one so that a next
column of said image can be processed; and

(d) means for producing a third sheared image corresponding to said output image
by performing said first shearing operation on said second sheared image.

9. An image processing device which provides an output image rotated
relative to an input image by an angle 8, said device comprising:

(a) means for providing an array of rows and columns of pixels representing the
input image;

(b) means for producing a fust sheared image by performing a fust shearing
operation on said array, said means for producing a first sheared image comprising:

(bl) means for initializing an integer column index c;

<b2) means for determining a vertical shear factor 0 - tan (6/2);

(b3) means for determining a horizontal offset AH defined as the product of
the vertical shear factor 0 times the column index c;

(b4) means for generating DCT coefficients of a segment of pixels related
to said column index c by taking a forward discrete even cosine transformation
(DCT) of said segment;

(b5) means for generating modified IDCT coefficients, corresponding to
shifted pixels, by performing a modified inverse discrete even cosine

"WO 96/36941 PCI/USJHtfOMM

transformation (IDCT) 0 f said DCT coefficients of said column index c using a
modified IDCT basis function dependent upon said vertical offset;

(c6) means for incrementing said column index c by one so mat a next
column of said image can be processed; and

(c) means for producing a second sheared image by performing a second shearing
operation on said first sheared image, said means for producing a second sheared image
comprising:

(cl) means for initializing an integer row index r;

(c2) means for determining a horizontal shear factor a » -sin 6;

(c3) means for determining a horizontal offset AH defined as the product of
the horizontal shear factor a times the row index r,

(c4) means for generating DCT coefficients of a segment of pixels related
to said row index r by taking a forward discrete even cosine transformation
(DCT) of said segment;

(c5) means for generating modified IDCT coefficients, corresponding to
shifted pixels, by performing a modified inverse discrete cosine transformation
(IDCT) of said DCT coefficients of said row index r using a modified IDCT
basis function dependent upon said vertical offset;

(c6) means for incrementing said row index r by one so that a next row of
said image can be processed; and

(d) means for producing a third sheared image corresponding to said output image
by performing said first shearing operation on said second sheared image.

10. An image processing method for skewing a segment of an image, said
image represented by pixels aligned in rows and columns in a spatial domain, said method
comprising the steps of:

selecting an image rotation angle;

initializing one of a column index and a row index;

determining a shear factor trigonometrical ly related to said image rotation angle;
determining an offset related to said shear factor and said one of the column index
and the row index;

WO 96/36941 PCT/US96/01418

generating DCT coefficients of the segment of pixels related to said one of the
column index and the row index by taking a forward discrete even cosine transformation
(DCT) of said segment; and

generating modified IDCT coefficients of said segment by taking a modified
inverse discrete even cosine transformation (IDCT) of said DCT coefficients, said
modified IDCT coefficients corresponding to said skewed segment of the image.

11. The image processing method of claim 10, further comprising the step of
generating said skewed segment of the image in response to said modified IDCT
coefficients.

12. An image processing method for skewing an image represented by pixels
aligned in rows and columns in a spatial domain, said method comprising the steps of:

(12a) in a microcomputer, selecting an image rotation angle 6;

(12b) in said microcomputer, initializing an integer row index r,

(12c) in said microcomputer, determining a horizontal shear factor be - -tan(0/2);

(12d) in said microcomputer, determining a horizontal offset AH defined as the
product of the horizontal shear factor a times the row index r,

(12e) in an array processor, generating DCT coefficients of a segment of pixels
related to said row index r by taking a forward discrete even cosine transformation
(DCT) of said segment;

(12f) in said array processor, generating modified IDCT coefficients corresponding
to shifted pixels by taking a modified inverse discrete even cosine transformation (IDCT)
of said DCT coefficients of said segment using a modified IDCT basis matrix dependent
upon said horizontal offset;

(12g) repeating steps (12e) and (12f) until said modified IDCT coefficients are
generated for every pixel corresponding to said row index r, and

(12h) incrementing said row index r by one, then repeating steps (12d) through
(12g) until said modified IDCT coefficients are generated for every pixel of the image.

13. The image processing method of claim 12, further comprising the step of
generating said skewed image in response to said modified IDCT coefficients:

WOJK/WMl PCT/US96/M418

14. An image processing method for skewing an image represented by pixels
aligned in rows and columns in a spatial domain, said method comprising the steps of:
(14a) in a microcomputer, selecting a predetermined image rotation angle 8;
(14b) in said microcomputer, initializing an integer column index c;
(14c) in said microcomputer, determining a vertical shear factor P » sin 8;
(14d) in said microcomputer, determining a vertical offset AV defined as the
product of the vertical shear factor P times the column index c;

(He) in an array processor, generating DCT coefficients of a segment of pixels
related to said column index c by taking a forward discrete even cosine transformation
(DCT) of said segment;

<14f) in said array processor, generating modified IDCT coefficients corresponding
to shifted pixels by taking a modified inverse discrete cosine transformation (IDCT) of
said DCT coefficients of said segment using a modified IDCT basis function dependent
upon said vertical offset;

(14g) repeating steps (14c) and (I4f) until said modified IDCT coefficients are
generated for every pixel corresponding to column index c; and

(14h) incrementing said column index c by one, then repeating steps (14d)
through (14g) until said modified IDCT coefficients are generated for every pixel of the
image.

15. The image processing method of claim 14, further comprising the step of
generating said skewed image in response to said modified IDCT coefficients.

16. An image processing method which provides an output image rotated
relative to an input image by an angle 8, said method comprising the steps of: .

(a) providing an array of rows and columns of pixels representing the input image;

(b) producing a first sheared image by performing a first shearing operation on said
array, said first shearing operation comprising the substeps of:

(bl) initializing an integer row index r,
(b2) determining a horizontal shear factor a - -tan(8/2);
(b3) determining a horizontal offset AH defined as the product of the
horizontal shear factor a times the row index r,

WO 96/36941 PCT/US96/014M

(b4) generating DCT coefficients, of a segment of pixels related to said row
index r, by taking a forward discrete even cosine transformation (DCT) of said

(b5) generating modified IDCT coefficients, corresponding to shifted pixels,
by performing a modified inverse discrete even cosine transformation (IDCT) of
said DCT coefficients of said row index r using a modified IDCT basis function
dependent upon said horizontal offset;

(b6) repeating steps (b4) and (b5) until said first modified IDCT coefficients
are generated for every pixel corresponding to said row index r,

(b7) incrementing said row index r by one, then repeating steps (b3)
through (b6) until said modified IDCT coefficients are generated for every pixel of
the image;

(c) producing a second sheared image by performing a second shearing operation
on said first sheared image, said second shearing operation comprising the sub steps of:

(cl) initializing an integer column index c;

(c2) determining a vertical shear factor B 30 sin 0;

(c3) determining a vertical offset AV defined as the product of the vertical
shear factor B times the column index c;

<c4) generating DCT coefficients of a segment of pixels related to said
column index c by taking a forward discrete even cosine transformation (DCT) of
said segment;

(c5) generating modified IDCT coefficients, corresponding to shifted pixels,
by performing a modified inverse discrete cosine transformation (IDCT) of said
DCT coefficients of said column index c using a modified IDCT basis function
dependent upon said vertical offset;

(c6) repeating steps (c4) and (cS) until said modified IDCT coefficients are
generated for every pixel corresponding to column index c; and

(c7) incrementing said column index c by one, then repeating steps (c2)
through (c6) until said modified IDCT coefficients are generated for every pixel of
the image; and

(d) producing a third sheared image corresponding to said output image by
performing said first shearing operation on said second sheared image.

PCT/OS9«m418

17. An image processing method which provides an output image rotated
relative to an input image by an angle 0, said method comprising the steps of:

(a) providing an array of rows and columns of pixels representing the input image;

(b) producing a first sheared image by performing a first shearing operation on said
array, said first shearing operation comprising the substeps of:

(bl) initializing an integer column index c;

(b2) determining a vertical shear factor p- tan (6/2);

(b3) determining a horizontal offset AH defined as the product of the
vertical shear factor P times the column index c;

(b4) generating DCT coefficients of a segment of pixels related to said
column index c by taking a forward discrete even cosine transformation (DCT) of
said segment;

(b5) generating modified IDCT coefficients, corresponding to shifted pixels,
by performing a modified inverse discrete even cosine transformation (IDCT) of
said DCT coefficients of said column index c using a modified IDCT basis
function dependent upon said vertical offset;

(b6) repeating steps (b4) and (bS) until said first modified IDCT coefficients
are generated for every pixel corresponding to said column index c;

(b7) incrementing said column index c by one, then repeating steps 0>2)
through (b6) until said modified IDCT coefficients are generated for every pixel of
the image;

(c) producing a second sheared image by performing a second shearing operation
on said first sheared image, said second shearing operation comprising die substeps of:

(cl) initializing an integer row index rj

(c2) determining a horizontal shear factor a " -sin 9;

(c3) determining a horizontal offset AH defined as the product of the
horizontal shear factor a times the row index r,

(c4) generating DCT coefficients of a segment of pixels related to said row
index r by taking a forward discrete even cosine transformation (DCT) of said
segment;

WO 96/36941 PCT/USSKW01418

(c5) generating modified IDCT coefficients, corresponding to shifted pixels,

by performing a modified inverse discrete cosine transformation (IDCT) of said

DCT coefficients of said row index r using a modified IDCT basis function

dependent upon said vertical offset;

(c6) shifting said segment of pixels related to said row index r and

repeating steps (c4) and (c5) until said modified IDCT coefficients are generated

for every pixel corresponding to said row index r;

(c7) incrementing said row index r by one, then repeating steps (c2)

through <c6) until said modified IDCT coefficients are generated for every pixel of

the image; and

(d) producing a third sheared image corresponding to said output image by
performing said first shearing operation on said second sheared image.

5)

WO 96/3*941

PCI7CS96/01418

2/11

FIG.2A
(PRIOR ART)

FIG. 2B
(PRIOR ART)

G000S278S

WO 96/36941

PCT/0S96/O1418

PCT/US96/01418

6/11

. SELECT 0

r»o
P rows
Q columns

a=-7

6

AN J

AH

SHIFT ROW r
BY AH

r =

r+1

end y

FIG. 4A

7/11

FROM BLOCK 444

446

TAK
OFF

= DCT
lOWr

TAKE
OF R

Ml DCT
OW r

456

TO BLOCK 443

PCTAJS96/01418

FIG. 4B

PC17US9fi/01418

8/11

FROM BLOCK 444

TO BLOCK 44a

FIG. 4C

WO 96/35941

PCT/US9«/01418

9/11

SELECT 0
C = 0

prows
Q columns

fi »

sin0

AV:

SHIFT COL. C
BY AV

C = C+1

FIG.5A

O00052783

WO 96/36941

PCT/US96701418

10/11

FROM BLOCK 504

TAKE OCT
OF COL C r 514

TAKE MIDCT
OF COL C

TO BLOCK SOS

FIG. 5B

WO 96/36941

PCT/US9«/01418

11/11

FROM BLOCK 504

TO BLOCK 522

FIG. 5C

INTERNATIONAL SEARCH REPORT

PCT/US 96/61418

C DOCUMENTS CONSIDERED TO «8 RELEVANT

W0.A.95 29461 (SARNOFF DAVID RES CENTER) 2
November 1995

see page 1, line 1 - page 3, line 5; claim

CVGIP: GRAPHICAL MODELS AND IMAGE
PROCESSING, JULY 1992, USA,
vol. 54, no. 4. ISSN 1049-9652,
pages 340-344, XP060288359
DAN1ELSS0N P E ET AL: "High-accuracy
rotation of images"

see page 348, right-hand column, paragraph
5 - page 341, left-hand column, paragraph

see page 342, right-hand column, paragraph
2 - paragraph 3

(3 f

[X"j Pttm* tuaiy mrabm mt tiDml fa man.

n of mean* of tt» iau

25. OK 96

Ewopon Punt Omo, P.B. nitPOoMim:
NL • ma hv Rlfenrifc

Td. ( ♦11-701 MO-JMO, T*. 31 651 niK,

Pierfederici, A

page 1 of 2

INTERNATIONAL SEARCH REPORT

PCT/US 96/91418

G(poafaattiea) DOCUMENTS CONSIDERED TP BE RELEVANT

nwttim rf -VrnmrnWi rHti totoatom wiwm »ppmpri«. iVttw rrtmni |Wi|»il

RdcmatMcItfanN*

A

PROCEEDINGS CVPR '86: IEEE COMPUTER
SOCIETY CONFERENCE ON COMPUTER VISION AND
PATTERN RECOGNITION (CAT. N0.86CH2299-5) ,
MIAMI BEACH, Ft, USA, 22-26 JUNE 1986,
ISBN 0-8186-8721-1, 1986, WASHINGTON, DC,
USA, IEEE COMPUT. SOC. PRESS, USA,
pages 272-277, XP60057226a
TANAKA A ET At: "A rotation method for
raster Image using skew transformation*
see the whole document

1-17

A

PROCEEDINGS OF GRAPHICS INTERFACE '86 AND
VISION INTERFACE '86, VANCOUVER, BC,
CANADA, 26-30 MAY 1986, 1986, TORONTO,
ONT. , CANADA, CANADIAN INF. PROCESS. SOC,
CANADA,

pages 77-81. XP90Q572832

PAETH A W: "A fast algorithm for general

raster rotation"

see the whole document

1-17

A

EP.A.9 433 645 (XEROX CORP) 26 June 1991

Fm PCT/ISA/31t (auiMMfM of mmm* HUM) (July tttj)

page 2 of 2

INTERNATIONAL SEARCH REPORT

Pa/US 96/01418

dtad in mroh raport

Paunt ftmfly
m«nbtr(t)

PubttaUion

dm

WO-A-9529461 92-11-95 ' NONE

US-A- 5111192 05-95-92
CA-A- 2027458 21-96-91
JP-A- 3290765 29-12-91